package a.codetop.笔试框架.天王;

public class 迷宫1_最短路径_起点到终点_可有障碍物 {

    //起点是1 ——走过的是88——> 终点是2 （障碍是-1==可走的是0）
    static int[][] g = {
        {0,-1,2,0},
        {0,0,0,-1},
        {0,-1,0,-1},
        {1,-1,0,0},
    };

    //所求
    static int stepMin=9999;

    public static void main(String[] args) {
        //找起点(若固定00起，删掉)
        for (int i=0;i<g.length;i++) {
            for (int j=0;j<g[0].length;j++) {
                if(g[i][j]==1){
                    qian(i,j);
                    //还原dfs的全局变量
                    step=0;
                }
            }
        }
        System.out.println("最少走 "+ stepMin +" 步");
    }

    //所求的tmp
    static int step=0;
    static int[][] fx={{-1,0},{1,0},{0,-1},{0,1}};

    static void qian(int i, int j) {
        pt(g);
        for (int k=0;k<fx.length;k++) {
            int x=i+fx[k][0],y=j+fx[k][1];
            //1、预判xy
            if(x<0||x>=g.length||y<0||y>=g[0].length||g[x][y]==88//越界+走过
                    || g[x][y]==-1 //其他不能走的情况
            ) continue;
            //2、终点xy
            if(g[x][y]==2){
                stepMin =Math.min(step, stepMin);
                continue;
            }
            //3、放心迭代xy
            int t=g[x][y];g[x][y]=88;    step=step+1;//步数=1,可改为花费的积分
            qian(x,y);
            g[x][y]=t;                   step=step-1;
        }
    }

    //debug↓————————————————————————————————————————————————————————————————————————————————————————————————————
    static void pt(int[][] p){
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[0].length; j++) {
                System.out.print(String.format("%3d",g[i][j]));
            }
            System.out.println();
        }
        System.out.println("——————————————————————————");
    }
}
